class Solution:
    def search(self, nums: list, target: int) -> int:
        # 如果列表为空直接返回 -1
        if len(nums) == 0:
            return 0

        # 二分法找到 target
        def binarySearch(nums: list, target: int) -> int:
            i = 0
            j = len(nums) - 1
            while i <= j:
                tmp = (i + j) // 2
                if nums[tmp] < target:
                    i = tmp + 1
                elif nums[tmp] > target:
                    j = tmp - 1
                else:
                    return tmp
            return None

        i = binarySearch(nums, target)
        if i is None:
            return 0

        count = 0
        j = i - 1
        while j >= 0 and nums[j] == target:
            count += 1
            j -= 1
        while i < len(nums) and nums[i] == target:
            count += 1
            i += 1

        return count

    def search2(self, nums: list, target: int) -> int:
        def helper(nums: list, target: int) -> int:
            """
            helper 函数专门用于查找 target 的右边界. 即查找仅比 target 大的数字的位置. 如果要查找左边界, 只需要
            用 target - 1 作为目标值即可. 因为查找右边界, 本质上查找的是排序数组中仅比 target 大的数字的位置. 由
            于数组中都是整数, 所以仅比 target - 1 大的数就是 target, 也就是 target 的左边界 + 1 的位置. 
            """
            i, j = 0, len(nums) - 1
            while i <= j:
                tmp = (i + j) // 2
                if nums[tmp] <= target: i = tmp + 1
                else: j = tmp - 1
            return j

        return helper(nums, target) - helper(nums, target - 1)


if __name__ == '__main__':
    solution = Solution()

    nums = [5, 7, 7, 8, 8, 10]
    target = 8
    print("Right:", nums.count(target))
    print("My:", solution.search(nums, target))
    print("My2:", solution.search2(nums, target))
    print("-------")

    nums = [1, 2, 3, 4, 5, 7, 7, 8, 8, 10]
    target = 8
    print("Right:", nums.count(target))
    print("My:", solution.search(nums, target))
    print("My2:", solution.search2(nums, target))
    print("-------")

    nums = [5, 7, 7, 8, 8, 10]
    target = 6
    print("Right:", nums.count(target))
    print("My:", solution.search(nums, target))
    print("My2:", solution.search2(nums, target))
    print("-------")

    nums = [1]
    target = 1
    print("Right:", nums.count(target))
    print("My:", solution.search(nums, target))
    print("My2:", solution.search2(nums, target))
    print("-------")

    print("Done!")
